Questão 11000 - Online judge

Ao ler problema, a fase mais difícil é perceber qual seria um possível algoritmo guloso que poderia gerar a sequência que seria a quantidade populacional de abelhas por sexo ao longo dos anos.

Após simulações para os primeiros valores da sequência, percebemos que a sequência resultado seria uma variação do algoritmo para gerar a sequência de fibonacci, diferenciando apenas a soma de uma unidade e a cada iteração, os dois valores anteriores ao final da sequência seriam a população total e de machos, nesta ordem.

Sequência de Fibonacci

Solução da questão

In [1]:
def get_result(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a+b+1
    return a, b

line = input()
while line.strip() != '-1':
    n = int(line.strip())
    print(*get_result(n))
    line = input()
1
1 2
2
2 4
5
12 20
10
143 232
20
17710 28656
40
267914295 433494436
-1

Solução alterada para gerar os gráficos

In [2]:
from sys import stdin
import numpy as np

total, males = np.array([]), np.array([])

a, b = 0, 1
while b < 2**32:
    a, b = b, a+b+1
    males = np.append(males, a)
    total = np.append(total, b)
    
females = total - males

Gráfico população primeiros 15 anos

In [3]:
import plotly.offline as py
import plotly.graph_objs as go

py.init_notebook_mode()

MAX_AND_MIN = 2**20

y = np.arange(1, 16)

layout = go.Layout(yaxis=go.layout.YAxis(title='Years'),
                   xaxis=go.layout.XAxis(
                       tickvals=[x for x in range(-MAX_AND_MIN, MAX_AND_MIN, 10**3)],
                       ticktext=[abs(x) for x in range(-MAX_AND_MIN, MAX_AND_MIN, 10**3)],
                       title='Bee Population'),
                   barmode='overlay',
                   bargap=0.1)

data = [go.Bar(y=y,
               x=males,
               orientation='h',
               name='Male',
               hoverinfo='x',
               marker=dict(color='powderblue')
               ),
        go.Bar(y=y,
               x=-females,
               orientation='h',
               name='Female',
               text=abs(females.astype('int')),
               hoverinfo='text',
               marker=dict(color='seagreen')
               )]

py.iplot(dict(data=data, layout=layout)) 

Gráfico população anos 35 - 45

In [4]:
import plotly.offline as py
import plotly.graph_objs as go

py.init_notebook_mode()

MAX_AND_MIN = 2**32

y = np.arange(35, 46)

layout = go.Layout(yaxis=go.layout.YAxis(title='Years'),
                   xaxis=go.layout.XAxis(
                       tickvals=[x for x in range(-MAX_AND_MIN, MAX_AND_MIN, 4*10**8)],
                       ticktext=[abs(x) for x in range(-MAX_AND_MIN, MAX_AND_MIN, 4*10**8)],
                       title='Bee Population'),
                   barmode='overlay',
                   bargap=0.1)

data = [go.Bar(y=y,
               x=males[35:],
               orientation='h',
               name='Male',
               hoverinfo='x',
               marker=dict(color='powderblue')
               ),
        go.Bar(y=y,
               x=-females[35:],
               orientation='h',
               name='Female',
               text=abs(females[35:].astype('int')),
               hoverinfo='text',
               marker=dict(color='seagreen')
               )]

py.iplot(dict(data=data, layout=layout)) 

Gráficos com foco na diferença entre o tamanho das populações

In [5]:
import plotly.offline as py
import plotly.graph_objs as go

py.init_notebook_mode()

anos = [str(x) for x in range(1, 45)]

trace1 = {"x": anos, 
          "y": females, 
          "marker": {"color": "pink", "size": 10}, 
          "mode": "markers", 
          "name": "Female", 
          "type": "scatter"
}

trace2 = {"x": anos, 
          "y": males, 
          "marker": {"color": "blue", "size": 10}, 
          "mode": "markers", 
          "name": "Male", 
          "type": "scatter", 
}

data = [trace1, trace2]
layout = {"title": "Bees population", 
          "xaxis": {"title": "Amount of individuals", }, 
          "yaxis": {"title": "Anos"}}

fig = go.Figure(data=data, layout=layout)
py.iplot(fig)

Referências

Questão 11000